package Ep06_BinaryTree.BFS.T5_0102;

import Ep06_BinaryTree.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/4/19 15:39
 * 说明：最基本的层序遍历
 */

public class Mine {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        // 起手剪枝
        if (root == null) return null;
        Deque<TreeNode> deque = new LinkedList<>();

        // 先把root放进去
        deque.offer(root);
        // 如果队列不空   --->   说明还没到叶子结点，下面还有层
        while (!deque.isEmpty()){
            // 用于存放各层value值的一维list
            List<Integer> itemList = new LinkedList<>();
            // 算出该层一共有几个节点，用于下面的本层节点poll的时候
            int size = deque.size();
            // size > 0 说明本层还有节点在队列中没有被poll出来
            while (size > 0){
                // 接收一下当前节点，用于后面作为父节点。如果不使用临时节点接收，就要交换root节点，很麻烦
                TreeNode tmpNode = deque.poll();
                // 把当前层的节点一个一个poll出来，同时记录他们的value
                itemList.add(tmpNode.val);
                // 左节点不空就把左节点offer进队列
                if (tmpNode.left != null){
                    deque.offer(tmpNode.left);
                }
                // 右节点不空就把左节点offer进队列
                if (tmpNode.right != null){
                    deque.offer(tmpNode.right);
                }
                // 由于poll出去了一个节点，所以要将队列中剩余当前层的节点数-1
                size--;
            }
            // 把各层记录数据的一维list加入到总res中，形成二维list，表示最终结果
            res.add(itemList);
        }
        return res;
    }
}
